//
// Created by TNJ on 2021/6/22.
//
#include "count_sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void count_sort(int *input, int input_length, int *output, int output_length){
    if(input == NULL || output == NULL || output_length < input_length){
        return;
    }

    int k = 0, max, min;
    int i = 0;

    min = input[0];
    max = input[0];
    //找出最大值和最小值
    for(i = 0; i < input_length; i++){
        if(input[i] < min){
            min = input[i];
        }
        if(input[i] > max){
            max = input[i];
        }
    }
    k = max - min + 1;  //求出数值区间
    int *temp = (int *)malloc(sizeof(int) * k);
    int *index = (int *)malloc(sizeof(int) * k);
    if(temp == NULL){
        return;
    }
    memset(temp, 0, sizeof(int) * k);
    memset(index, -1, sizeof(int) * k);
    int count = 0;
    for(i = 0; i < input_length; i++){
        temp[input[i] - min]++;  //统计input里每个元素的个数
    }

    for(i = 0; i <= k; i++){
        count = temp[i];
        if(i > 0){
            temp[i] = temp[i] + temp[i - 1];  //统计input小于等于各个元素值的个数
        }
        if(count > 0){
            index[i] = temp[i] - count;  //求出各个元素在输出序列中对应的索引值
        }
    }
    for(i = input_length - 1; i >= 0; i--){
        output[index[input[i] - min]] = input[i];  //将原始序列中的元素存放在输出序列对应索引中
        index[input[i] - min]++;  //相同的数据相邻放置
        temp[input[i] - min]--;
    }
    free(temp);
    free(index);
}
